#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using pii = pair < int , int >;
using vec = vector < int >;
using veg = vector < pii >;
using ll = long long;
using db = double;
using tl = tuple < int, int, int >;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 1e6 + 10;

int fa[N], a[N], n, siz[N];
ll ans;
tl ed[N];

int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }

void work() {
	rep(i, 1, n) fa[i] = i, siz[i] = 1;
	rep(i, 1, n - 1) get<0>(ed[i]) = max(a[get<1>(ed[i])], a[get<2>(ed[i])]);
	sort(ed + 1, ed + n);
	rep(i, 1, n - 1) {
		int x = get<1>(ed[i]), y = get<2>(ed[i]);
		if(gf(x) ^ gf(y)) {
			ans += 1ll * get<0>(ed[i]) * siz[gf(x)] * siz[gf(y)];
			siz[gf(x)] += siz[gf(y)]; fa[gf(y)] = gf(x);
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
	n = in; rep(i, 1, n) a[i] = in;
	rep(i, 1, n - 1) { int u = in, v = in; ed[i] = make_tuple(min(a[u], a[v]), u, v); }
	work(); rep(i, 1, n) a[i] = -a[i]; work();
	printf("%lld\n", ans); return 0;
}
